package demo03On;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 13
 * Time:16:07
 */

import java.util.Arrays;

/***
 * 三.复杂度——衡量一个算法的效率的；
 * 时间效率——时间复杂度；
 * 空间效率——空间复杂度
 * 大O的渐进法表示；问题规模：N
 * 1.时间复杂度：算法中基本的操作的执行次数，称为算法的时间复杂度
 *
 * 2.时间复杂度的计算：
 * （1）用常数1 取代运行时间中的所有加法常数；
 * （2）在修改后的运行次数函数中，只保留最高阶项；
 * （3)如果最高阶项存在且不是1，则去除与此项相乘的常数，得到的结果就是大O阶；
 *
 * 3.空间复杂度：对一个算法在运行过程中临时占用存储空间大小的度量；空间复杂度算的是变量的个数
 * 空间复杂度：完成该算法额外进行开辟的空间
 */
public class Complicated {
    /***
     * 5.非递归实现fibnacci
     * 空间复杂度O(N)
     * @return
     */
    public long[] fibnacci1(int n){
        long[] fibArray = new long[n + 1];//额外的申请了一个数组空间，空间复杂度为O(N)
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }
        return fibArray;
    }
    /***
     * 4.计算斐波那契递归fibonacci的时间复杂度？O(2 ^ n)——不适合使用递归实现
     * 2 ^ n - 1
     * @param N
     * @return
     */
    public int fibonacci(int N){
        return  N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
    }
    /***
     * 3.计算阶乘递归factorial的时间复杂度?
     * 求递归的次数——N——O(N)
     * @param N
     * @return
     * 递归：每次都申请开辟空间保存值【递归几次就要开辟几个栈帧】，空间复杂度——O(N)
     */
    public long factorial(int N){
        return  N < 2 ? N : factorial(N - 1) * N;
    }

    /***
     * 2.二分查找法时间复杂度：O(logn)
     * n个数  找次数b
     * 2        2
     * 4        3
     * 8        4
     * 。。。
     * n = 2^(b - 1)
     * =>  b = logn + 1
     *
     */
    public int binarySearch(int[] arr, int key){
        int begin = 0;
        int end = arr.length - 1;
        while(begin <= end){
            int mid = begin + ((end - begin) / 2);
            if(arr[mid] < key) {
                begin = mid + 1;
            }else if(arr[mid] > key){
                end = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    /***
     * 1.优化之后的冒泡排序算法的时间复杂度：
     * n * (n - 1) ——> n ^2 - n——> n ^2【最坏情况】
     * 最坏情况：O(n^2)
     * 最好情况：O(n - 1)——>O(n)
     * @param arr
     * 空间复杂度O(1)
     */
    public static void bubbleSort(int[] arr){
        for(int end = arr.length;end > 0;end--){//N
            boolean sorted = true;
            for (int i = 1; i < end; i++) {// N - 1
                if(arr[i - 1] > arr[i]){
                    swap(arr,i - 1,i);
                    sorted = false;
                }
            }
            if(sorted == true){
                break;
            }
        }
    }

    private static void swap(int[] arr, int i, int i1) {
        if(arr[i] > arr[i1]){
            int tmp = arr[i];
            arr[i] = arr[i1];
            arr[i1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,6,3,2};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
